// Range v3 library
//
//  Copyright Eric Niebler 2014
//
//  Use, modification and distribution is subject to the
//  Boost Software License, Version 1.0. (See accompanying
//  file LICENSE_1_0.txt or copy at
//  http://www.boost.org/LICENSE_1_0.txt)
//
// Project home: https://github.com/ericniebler/range-v3

//===----------------------------------------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is dual licensed under the MIT and the University of Illinois Open
// Source Licenses. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#include <nanorange/algorithm/stable_sort.hpp>
#include <cassert>
#include <memory>
#include <random>
#include <vector>
#include <algorithm>
#include "../catch.hpp"
#include "../test_utils.hpp"
#include "../test_iterators.hpp"

namespace stl2 = nano::ranges;

namespace {

std::mt19937 gen;

struct indirect_less
{
	template <class P>
	bool operator()(const P& x, const P& y) const
		{return *x < *y;}
};

template <class RI>
void
test_sort_helper(RI f, RI l)
{
	using value_type = stl2::iter_value_t<RI>;
	auto stable_sort = make_testable_1<false>([](auto&&... args) {
		return stl2::stable_sort(std::forward<decltype(args)>(args)...);
	});
	if (f != l)
	{
		long len = l - f;
		value_type* save(new value_type[len]);
		do
		{
			std::copy(f, l, save);
			stable_sort(save, save+len).check([&](int *res)
			{
				CHECK(res == save+len);
				CHECK(std::is_sorted(save, save+len));
				std::copy(f, l, save);
			});
			stable_sort(save, save+len, std::greater<int>{}).check([&](int *res)
			{
				CHECK(res == save+len);
				CHECK(std::is_sorted(save, save+len, std::greater<int>{}));
				std::copy(f, l, save);
			});
		} while (std::next_permutation(f, l));
		delete [] save;
	}
}

template <class RI>
void
test_sort_driver_driver(RI f, RI l, int start, RI real_last)
{
	for (RI i = l; i > f + start;)
	{
		*--i = start;
		if (f == i)
		{
			test_sort_helper(f, real_last);
		}
		if (start > 0)
			test_sort_driver_driver(f, i, start-1, real_last);
	}
}

template <class RI>
void
test_sort_driver(RI f, RI l, int start)
{
	test_sort_driver_driver(f, l, start, l);
}

template <int sa>
void
test_sort_()
{
	int ia[sa];
	for (int i = 0; i < sa; ++i)
	{
		test_sort_driver(ia, ia+sa, i);
	}
}

void
test_larger_sorts(int N, int M)
{
	assert(N > 0);
	assert(M > 0);
	// create array length N filled with M different numbers
	int* array = new int[N];
	int x = 0;
	for (int i = 0; i < N; ++i)
	{
		array[i] = x;
		if (++x == M)
			x = 0;
	}

	// test saw tooth pattern
	CHECK(stl2::stable_sort(array, array+N) == array+N);
	CHECK(std::is_sorted(array, array+N));
	// test random pattern
	std::shuffle(array, array+N, gen);
	CHECK(stl2::stable_sort(array, array+N) == array+N);
	CHECK(std::is_sorted(array, array+N));
	// test sorted pattern
	CHECK(stl2::stable_sort(array, array+N) == array+N);
	CHECK(std::is_sorted(array, array+N));
	// test reverse sorted pattern
	std::reverse(array, array+N);
	CHECK(stl2::stable_sort(array, array+N) == array+N);
	CHECK(std::is_sorted(array, array+N));
	// test swap ranges 2 pattern
	std::swap_ranges(array, array+N/2, array+N/2);
	CHECK(stl2::stable_sort(array, array+N) == array+N);
	CHECK(std::is_sorted(array, array+N));
	// test reverse swap ranges 2 pattern
	std::reverse(array, array+N);
	std::swap_ranges(array, array+N/2, array+N/2);
	CHECK(stl2::stable_sort(array, array+N) == array+N);
	CHECK(std::is_sorted(array, array+N));
	delete [] array;
}

void
test_larger_sorts(unsigned N)
{
	test_larger_sorts(N, 1);
	test_larger_sorts(N, 2);
	test_larger_sorts(N, 3);
	test_larger_sorts(N, N/2-1);
	test_larger_sorts(N, N/2);
	test_larger_sorts(N, N/2+1);
	test_larger_sorts(N, N-2);
	test_larger_sorts(N, N-1);
	test_larger_sorts(N, N);
}

struct S
{
	int i, j;
};

}

TEST_CASE("alg.stable_sort")
{
	// test null range
	int d = 0;
	int * r = stl2::stable_sort(&d, &d);
	CHECK(r == &d);
	// exhaustively test all possibilities up to length 8
	test_sort_<1>();
	test_sort_<2>();
	test_sort_<3>();
	test_sort_<4>();
	test_sort_<5>();
	test_sort_<6>();
	test_sort_<7>();
	test_sort_<8>();

	test_larger_sorts(15);
	test_larger_sorts(16);
	test_larger_sorts(17);
	test_larger_sorts(256);
	test_larger_sorts(257);
	test_larger_sorts(499);
	test_larger_sorts(500);
	test_larger_sorts(997);
	test_larger_sorts(1000);
	test_larger_sorts(1009);

	// Check move-only types
	{
		std::vector<std::unique_ptr<int> > v(1000);
		for(int i = 0; (std::size_t)i < v.size(); ++i)
			v[i].reset(new int(v.size() - i - 1));
		stl2::stable_sort(v, indirect_less());
		for(int i = 0; (std::size_t)i < v.size(); ++i)
			CHECK(*v[i] == i);
	}

	// Check projections
	{
		std::vector<S> v(1000, S{});
		for(int i = 0; (std::size_t)i < v.size(); ++i)
		{
			v[i].i = v.size() - i - 1;
			v[i].j = i;
		}
		stl2::stable_sort(v, std::less<int>{}, &S::i);
		for(int i = 0; (std::size_t)i < v.size(); ++i)
		{
			CHECK(v[i].i == i);
			CHECK((std::size_t)v[i].j == v.size() - i - 1);
		}
	}

	// Check rvalue range
	{
		std::vector<S> v(1000, S{});
		for(int i = 0; (std::size_t)i < v.size(); ++i)
		{
			v[i].i = v.size() - i - 1;
			v[i].j = i;
		}
		auto r = stl2::stable_sort(std::move(v), std::less<int>{}, &S::i);
		static_assert(stl2::same_as<decltype(r), stl2::dangling>);
		for(int i = 0; (std::size_t)i < v.size(); ++i)
		{
			CHECK(v[i].i == i);
			CHECK((std::size_t)v[i].j == v.size() - i - 1);
		}
	}
}
